import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) {

        BST<Integer> bst = new BST<>();
        //int[] nums = {5, 3, 6, 8, 4, 2};
        //for(int num: nums)
            //bst.add(num);

        /////////////////
        //      5      //
        //    /   \    //
        //   3    6    //
        //  / \    \   //
        // 2  4     8  //
        /////////////////

        //前序遍历
        //bst.preOrder();//5 3 2 4 6 8

        //非递归前序遍历
        //bst.preOrderNR();//5 3 2 4 6 8

        //中序遍历
        //bst.inOrder();//2 3 4 5 6 8

        //后序遍历
        //bst.postOrder();//2 4 3 8 6 5

        //层序遍历
        //bst.levelOrder();// 5 3 6 2 4 8

        //System.out.println(bst);

        Random random = new Random();
        int n = 1000;

        // test removeMin
        for(int i = 0 ; i < n ; i ++)
            bst.add(random.nextInt(10000));

        ArrayList<Integer> nums = new ArrayList<>();
        while(!bst.isEmpty())
            nums.add(bst.removeMin());

        System.out.println(nums);
        for(int i = 1 ; i < nums.size() ; i ++)
            if(nums.get(i - 1) > nums.get(i))
                throw new IllegalArgumentException("Error!");
        System.out.println("removeMin test completed.");



        // test removeMax
        for(int i = 0 ; i < n ; i ++)
            bst.add(random.nextInt(10000));

        nums = new ArrayList<>();
        while(!bst.isEmpty())
            nums.add(bst.removeMax());

        System.out.println(nums);
        for(int i = 1 ; i < nums.size() ; i ++)
            if(nums.get(i - 1) < nums.get(i))
                throw new IllegalArgumentException("Error!");
        System.out.println("removeMax test completed.");

    }
}